4. ネットワークデータのビジュアライゼーション

ネットワークデータのビジュアライゼーション

増井俊之

慶應義塾大学 環境情報学部

masui@pitecan.com

2017年10月19日

InfoGraphicsの例

http://portal.nifty.com/2016/10/19/a/img/pc/02.jpg

https://gyazo.com/6569fe450539f66aaff3f6cd424bf74c.png

台湾の線路

https://gyazo.com/373f5eb2e488c546858cdaca48520515.png

ネットワークデータとは

ノード(節点)とエッジ(辺)の集合

http://upload.wikimedia.org/wikipedia/commons/5/57/6n-graf.png

ネットワークデータの種類

有向グラフ

階層情報も含む

無向グラフ

https://gyazo.com/ad1de9de3d4be1125253e1336480a5a2.png

完全グラフ

https://gyazo.com/25af21cadfdbd46c9994e21dac385782.png

視覚化例: 複雑なネットワーク

https://gyazo.com/da0643aa81e47595e05b192da61240dd.png

視覚化例: Scrapbox

https://gyazo.com/d9ecae834299285efc9bba3fc1b889c4

D3.jsの force layout を利用

視覚化例: LSIレイアウト

https://gyazo.com/270bc4656134809b354a3d709a01510e.png

Beautiful Visualization

http://gyazo.com/efc62e15710c46f8c5640b6148390db0.png

長い歴史

Graph Drawingコンファレンス

https://gyazo.com/3965de9f4446cf0c49114d74669e1e05.png

https://gyazo.com/a7fd8a62265562359bbeec3c7f6df258.png

大規模なネットワーク情報の例

有向グラフ

Webのリンク, 状態遷移図, Twitterのフォロー関係

無向グラフ

マイミク関係, 友達関係

二部グラフ

本棚, コミュ参加関係

二部グラフ

ふたつの集合間のリンク関係

https://gyazo.com/9d95e3571e8873a0d97c444ebf950ff8.png

表として表現できるグラフ

mixiのコミュ情報

A氏 ⇔ コミュX ⇔ B氏

コミュを介してA氏とB氏が関連

A氏の本棚 ⇔ 書籍 ⇔ B氏の本棚

https://gyazo.com/d90cb6991ba0839c7c8c959c7f48414d.png

表形式だがネットワーク的に表現可能

https://gyazo.com/e408bec06444bdf845db1817077709f9.png

本-本棚ネットワーク

https://gyazo.com/f5973af08f60e72f4b958e7aa98622d2.png

人物と参加イベントのグラフ

https://gyazo.com/3c3aa973ceaf30174937c149eedf2dde.png

イベント参加情報から計算した人物間の関連

https://gyazo.com/ae2652279a7a2075229767f575088a60.png

アメリカ上院の投票関係

同じ投票傾向の人物を線で結んだもの

https://gyazo.com/48ab0ee6b79784d72ab6eeed25edb5e7.png

ネットワーク情報の特徴

平面グラフでないのが普通

木構造はすべて平面グラフ

平面グラフ

エッジが重ならない図を描けるグラフ

特定の構造を含むと非平面グラフになる

平面グラフにならない図

https://gyazo.com/33734994f80132eada3bf2d4e7089627.png

平面グラフの例

ネットワークデータの美的配置

エッジが重ならないように配置

ノードが重ならないように配置

最善の配置の計算には指数時間必要

c.f. 2点を結ぶものの集合だと簡単な計算でエッジの重なりを除去可能

重なってたらエッジを入れ換える

ネットワークデータの平面レイアウト

統計的手法

「ばねモデル」が基本

様々なバリエーションあり

e.g. 鎌田/川合の方法

ばねモデル資料

Eadesのアルゴリズム

隣接ノード間のスプリング力 + 隣接していないノード間の反発力

https://gyazo.com/7bf72f55fdad20a6bbfd3a712a93310b.png

最短経路長がばねの長さになるようにする

漸進的に配置を高速計算

吸引力はばね式/反発力は電気式

https://gyazo.com/6c7ae678108594823bcdee2bd7570260.png

鎌田/川合アルゴリズム

http://masui.org/a9166c9b8e8850d5237edecc23e437b1.gif

元Access社社長

Compact HTMLを開発した

現在は「スタートアップ・ブースター」

https://gyazo.com/0a1130c0369c174553a5f8b5f886fafb.png

NTT山田氏のシステム

ある程度遠いものは考慮しない

https://gyazo.com/b7aff995ab7a0b4d9720c609a3fa683a.png

階層的に分割する方法

https://gyazo.com/d86d7e0e16e7258b0ff9d5b626a7991b.png

https://gyazo.com/fa8f657c3d131d7514ba14e3b3cff85e.png

制約解決システム

ばねモデルは制約解決システム

ばねの長さに関する沢山の制約を解く

レイアウト制約の例

https://gyazo.com/101b33ff7784c1fb76c678d719a1d9b2.png

様々な制約解決アルゴリズムの研究

等式/不等式を高速に解く

ビデオ: Chorus (細部)

https://gyazo.com/1195203d4865c2d4b6c1506870aaa115.png

ビデオ: AGI (細部)

https://gyazo.com/7117e3f941b21e761b3de83750f8a803.png

統計的/確率的手法

GA (遺伝的アルゴリズム)

SA (Simulated Annealing)

遺伝的アルゴリズム

生物進化を計算機上でシミュレーション

解を「ゲノム」にコーディング

世代交替により良い解を残していく

遺伝的アルゴリズム

ランダムに生成したN個の個体を用意

code:c

while(1){

現世代の各個体の適応度を計算

確率的に以下の動作を行い結果を次世代に保存

個体を二つ選択して交叉を行う

個体を一つ選択して突然変異を行う

個体を一つ選択してそのままコピーする

次世代の個体数が N 個になるまで繰り返す

現世代の個体を次世代のもので置き換える

}

世代交替における遺伝子操作

交叉

突然変異

一点交叉

https://gyazo.com/fc41eca4275cac628ded90bc347ad1f5.png

二点交叉

https://gyazo.com/88c894a29d5c22e1b59b711ffe42ad5b.png

一様交叉

https://gyazo.com/77ea3c2cbc95253934ff55e49b5fab5a.png

レイアウトの評価値計算

https://gyazo.com/fb926b172e65f7010905eda402e2ae6f.png

遺伝的演算

https://gyazo.com/fd6a0485f7ac715321aa86935bf25542.png

LSIレイアウトなどに適用

https://gyazo.com/270bc4656134809b354a3d709a01510e.png

大規模視覚化における問題

データが密集しがち

思ったところに配置できない

グラフの構造が少しでも変化すると配置が大きく変わる

対策

対話性を利用

表示量を間引く

対話性の利用

完全自動配置をやめる

人間がある程度配置を行なう

動的に表示を変える

「納豆ビュー」のような方法

対話的レイアウト

完全自動にするのではなく、人手で制約指定

対話的GAによるレイアウト

https://gyazo.com/8957332d0b32ca91bf2575fb663b1839.png

表示量の制御

あらゆるエッジを利用するのをやめる

重要そうなリンクだけ使って木構造になる

その他のネットワーク視覚化

FisheyeView

納豆ビュー

Kartoo

Musicplasma

Textarc

FisheyeView

視点の付近はすべて表示を行ない、視点から遠いものは重要なもののみ表示する

「重要さ関数」選択により各種の視覚化が可能

Degree of Interest = A Priori Interest - Distance

ビデオ: FisheyeViewGraph

https://gyazo.com/f228408d3c5daf4d76ef96b1633a40bb.png

VIVE

キーワードをノードとして文書検索

https://gyazo.com/6b11c24d515294ea19b21d96f660a5d8.png

納豆ビュー

ノードを引っ張って動きを観察

https://gyazo.com/d731d9c83f2d087051062d1d9893c665.png

関連するWebサイトとキーワードを海図のように表示する

https://gyazo.com/e237efc0c3e88d03f00348a305866d33.png

好きな音楽アーティストに似たアーティストは誰？

https://gyazo.com/0c00cd4ab0195413838a5833fabdf1f0.png

ハムレットに登場する単語の関係図

https://gyazo.com/b5e6d1d75a05e904a4cde4ffe5604a3a.png

https://gyazo.com/5b446276ede34af0610cb92f73e79e6e.png

リンクスパムの視覚化

https://gyazo.com/948f6cadcc08da8f4b051468fa42484b.png

まとめ

階層構造で表現できないデータの視覚化

ばねモデルとGAが一般的

Webのデータを視覚化する美しいシステムが多数出現中

課題1

階層型データまたはネットワーク型データの視覚化

ソフト利用または手書き

http://gyazo.com/b85ecf16d0d23bf6d9907e40a95ea5cc.png